from typing import List


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        f = [[True] * n for _ in range(n)]
        index = [1 << i for i in range(n - 2, -1, -1)]

        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                f[i][j] = (s[i] == s[j]) and f[i + 1][j - 1]

        ret = list()

        def dfs(i: int, num):
            if i == n:
                cur = []
                last_cut = 0
                cur_cut = 0
                while num != 0:
                    while num < index[cur_cut]:
                        cur_cut += 1
                    num -= index[cur_cut]
                    cur_cut += 1
                    cur.append(s[last_cut: cur_cut])
                    last_cut = cur_cut
                cur.append(s[cur_cut:])
                ret.append(cur)
                return

            for j in range(i, n):
                if f[i][j]:
                    rec = 0
                    if j != n - 1:
                        rec = index[j]
                    dfs(j + 1, num + rec)

        dfs(0, 0)
        return ret


if __name__ == '__main__':
    s = Solution()
    r = s.partition('aab')
    print(r)
